Зараз я пишу базовий синтаксичний аналізатор для смаку XML. Як вправу я застосовую синтаксичний аналізатор таблиці LL. Це мій приклад граматики BNF: % рядок даних імені маркера %% / * LL (1) * / doc: елем elem: "<" open_tag open_tag: ім'я attr close_tag close_tag: ">" elem_or_data "" | "/>" ; elem_or_data: "<" відкрити_тег elem_or_data | дані elem_or_data | / * епсилон * / ; attr: name ":" рядок attr | / * епсилон * / ; Чи правильно ця граматика? Кожен літерал терміналу знаходиться між лапками. Абстрактні термінали визначаються маркером%. Я кодую рукописний лексер, щоб перетворити свої дані в список лексем. Як мені позначити абстрактні термінали?
2021-03-03 08:12:20
Класичним підходом було б написати регулярний вираз (або інший розпізнавач) для кожного можливого терміналу.
Те, що ви називаєте "абстрактними" терміналами, які є абсолютно конкретними, насправді є терміналами, асоційовані шаблони яких розпізнають більше одного можливого вхідного рядка. Рядок, який фактично розпізнаний (або якась обчислювана функція цього рядка), повинен бути переданий синтаксичному аналізатору як семантичне значення маркера.
Номінально в кожній точці вхідного рядка токенизатор запускає всі розпізнавачі та вибирає той, що має найдовший збіг. (Це так зване правило "максимального гризу".) Це зазвичай можна оптимізувати, особливо якщо всі шаблони є регулярними виразами. (F) lex зробить цю оптимізацію за вас, наприклад.
Ускладнення у вашій справі полягає в тому, що лексема вашої мови залежить від контексту. Зокрема, коли ціллю є elem_or_data, єдиними можливими маркерами є <,